package 每日一题;

import javax.management.QueryEval;
import java.util.LinkedList;
import java.util.Queue;

public class Date0108 {

    /**
     * 自解：额外需要一个队列 将数组倒序存入 循环k次
     * 每一次就是将出队 入队
     *--耗时 耗空间
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i=nums.length-1;i>=0;i--){
            queue.add(nums[i]);

        }

        while (k>0){
            int out = queue.poll();
            queue.add(out);
            k--;
        }

        for (int i=nums.length-1;i>=0;i--){
            nums[i] = queue.poll();
        }

    }

    /**
     * 题解：原地修改，整个过程可以理解会不停的反转
     * 首先全部反转
     * 在反转前k的 再反转后面的
     * ---k考虑大于n 的情况
     * 因为k=n时又转回去了 所以就反转k mod n
     *
     */

    public void rotate1(int[] nums, int k) {

        if (nums.length>1){
            k %= nums.length;
            reverse(nums,0,nums.length-1);
            reverse(nums,0,k-1);
            reverse(nums,k,nums.length-1);
        }



    }
    public void reverse(int[] nums,int start,int end){
        while (start<end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start++;
            end--;
        }
    }

}
